﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ShortestPath
{
    public class HeapNode : IComparable//最小堆结点表示
    {
        public int i;   // vertex number
        public float length;// current length

        public HeapNode(int ii, float ll)
        {
            i = ii;
            length = ll;
        }

        public int CompareTo(Object x)
        {
            float xl = ((HeapNode)x).length;
            if (length < xl) return -1;
            if (length == xl) return 0;
            return 1;
        }
    }

    class BBShortest
    {
        public static void shortest(int v, float[] dist, int[] p, int[,] a)
        {//求最短路径
            int n = p.Length - 1;
            BinaryHeap heap = new BinaryHeap();
            HeapNode enode = new HeapNode(v, (float)0);

            for (int j = 1; j <= n; j++)
                dist[j] = float.MaxValue;

            dist[v] = 0;

            while (true)
            {
                for (int j = 1; j <= n; j++)
                    if (a[enode.i, j] < float.MaxValue
                        && enode.length + a[enode.i, j] < dist[j])
                    {
                        dist[j] = enode.length + a[enode.i, j];
                        p[j] = enode.i;
                        HeapNode node = new HeapNode(j, dist[j]);
                        heap.insert(node);
                    }
                if (heap.isEmpty()) break;
                else enode = (HeapNode)heap.deleteMin();
            }
        }
    }
}
